#include <iostream>
using namespace std;
#define maxSize_stack 10
#define maxSize_queue 10
typedef struct node
{
	char *data;
	struct node *lchild, *rchild;
}BiNode, *BiTree;
typedef struct stack
{
	BiTree data[maxSize_stack];
	int top;
}SqStack;
typedef struct queue
{
    BiTree data[maxSize_queue];
    int front,rear;
}SqQueue;

SqStack s;//全局栈
SqQueue q;//全局队列

/*栈初始化*/
void InitStack(SqStack &s) {
	s.top = -1;
}
/*判断栈空*/
bool StackEmpty(SqStack &s) {
	if (s.top == -1) {
		return true;
	}
	else {
		return false;
	}
}
/*入栈*/
bool Push(SqStack &s, BiTree x) {
	if (s.top == maxSize_stack - 1) {
		return false;//栈满，报错
	}
	s.data[++s.top] = x;
	return true;
}
/*出栈*/
bool Pop(SqStack &s, BiTree &x) {
	if (s.top == -1) {
		return false;//栈空，报错
	}
	x = s.data[s.top--];
	return true;
}
/*读栈顶元素*/
bool GetTop(SqStack &s, BiTree &x) {
	if (s.top == -1) {
		return false;//栈空，报错
	}
	x = s.data[s.top];
	return true;
}

/*初始化队列*/
void InitQueue(SqQueue &q){
    q.front=q.rear=0;
}
/*判断队列是否为空*/
bool QueueEmpty(SqQueue &q){
    if(q.rear==q.front){
        return true;
    }
    else{
        return false;
    }
}
/*入队*/
bool EnQueue(SqQueue &q,BiTree x){
    if((q.rear+1)%maxSize_queue==q.front){
        return false;//队满，报错
    }
    q.data[q.rear]=x;
    q.rear=(q.rear+1)%maxSize_queue;
    return true;
}
/*出队*/
bool DnQueue(SqQueue &q,BiTree &x){
    if(q.rear==q.front){
        return false;//空队，报错
    }
    x=q.data[q.front];
    q.front=(q.front+1)%maxSize_queue;
    return true;
}

/*先序创建二叉树*/
BiTree CreateTree(BiTree &T)
{
	char *x;
	scanf("%c", &x);
	if (*x == '#')
		T = NULL;
	else {
		T = (BiTree)malloc(sizeof(BiNode));
		if (!T) return 0;
		T->data = x;
		CreateTree(T->lchild);
		CreateTree(T->rchild);
	}
	return T;
}
void PreOrder(BiTree T){
    InitStack(s);
	BiNode *p = T;
	while (p || !StackEmpty(s)) {
		if (p) {
            printf("%c", p->data);
			Push(s, p);
			p = p->lchild;
		}
		else {
			Pop(s, p);
			p = p->rchild;
		}
	}
	printf("\n");
}
void InOrder(BiTree T) {
	InitStack(s);
	BiNode *p = T;
	while (p || !StackEmpty(s)) {
		if (p) {
			Push(s, p);
			p = p->lchild;
		}
		else {
			Pop(s, p);
			printf("%c", p->data);
			p = p->rchild;
		}
	}
}
void PostOrder(BiTree T){
    InitStack(s);
    BiNode *p=T;
    BiNode *r=NULL;
    while (p||!StackEmpty(s))
    {
        if(p){
            Push(s,p);
            p=p->lchild;
        }
        else{
            GetTop(s,p);
            if(p->rchild&&p->rchild!=r){
                p=p->rchild;
                Push(s,p);
                p=p->lchild;
            }
            else{
                Pop(s,p);
                printf("%c", p->data);
                r=p;
                p=NULL;
            }
        }
    }
}
void LevelOrder(BiTree T){
    InitQueue(q);
    BiNode *p;
    EnQueue(q,T);
    while (!QueueEmpty(q))
    {
        DnQueue(q,p);
        printf("%c", p->data);
        if(p->lchild!=NULL){
            EnQueue(q,p->lchild);
        }
        if(p->rchild!=NULL){
            EnQueue(q,p->rchild);
        }
    }
}
int Depth(BiTree T)/* 深度 */
{
    if(T==NULL)
        return(0);
    return 1+(Depth(T->lchild)>Depth(T->rchild)? Depth(T->lchild):Depth(T->rchild));
}
void Long(BiTree T)
{
    if(T!=NULL)
    {
        printf("%c ",T->data);//访问节点
        if(Depth(T->lchild)>Depth(T->rchild))//如果左边高度大于右边，往左走，否则右走。
            Long(T->lchild);
        else
            Long(T->rchild);
    }
}
/*ABD##E##C##*/
int main()
{
	BiNode *root;//定义一个根节点
	CreateTree(root);
    PreOrder(root);
	printf("%d\n",Depth(root));
	Long(root);
}